/***************************************************************************************
 *                      R*-Tree的使用说明：
 * 1.构建
 *   构建R*-Tree时需要指定维度(dimension)、最小子节点数(m)、及最大子节点数(M)。
 *   其中： 2 ≤ dimension;   2 ≤ m ≤ M/2;
 *   示例：
 *      构建2维，最小节点数为2，最大节点数为4，叶子数据类型为Int32的树.
 *          RStarTree<Int32> tree = new RStarTree<Int32>(2, 2, 4);
 * 2.插入
 *     向树中插入叶子时，需要为叶子指定包围盒大小。包围盒大小由各维度范围构成的序列
 *   指定，例如X维度的最小值为minX，最大值为maxX; Y维度的最小值为minY，最大值为maxY，
 *   则包围盒序列为： [minX, maxX, minY, maxY]
 *   示例：
 *       插入值为5，X维度范围为[0, 10]，Y维度范围为[15， 30]的叶子.
 *          Double[] bound = {0, 10, 15, 30};
 *          tree.Insert(5, bound);
 * 3.查询
 *     如果不指定范围，则查询并返回所有叶子；
 *     如果指定范围，通过设定查询方式返回满足条件的叶子。
 *   示例：
 *       查询所有叶子：
 *          Int32[] all = tree.Search();
 *       指定查询范围：X维度范围为[5, 15]，Y维度范围为[10, 25]
 *          Double[] searchBound = {5, 15, 10, 25};
 *       查询在范围内部或与范围相交的叶子：
 *          Int32[] overlapped = tree.Search(searchBound, RTreeSearchMode.Overlapped);
 *       查询完全在范围内部的叶子：
 *          Int32[] enclosed   = tree.Search(searchBound, RTreeSearchMode.Enclosed);
 * 4.删除
 *     有两种删除方式：
 *         删除指定叶子：只删除同指定叶子相同的节点
 *         删除指定范围内叶子：所有完全包含在指定范围内部的叶子均被删除
 *   示例：
 *       删除指定叶子：删除值为5的叶子，如果指定删除重复项，则删除所有值为5的节点
 *          Int32 removedNum = tree.Remove(5, true);
 *       删除指定范围内叶子：删除X维度范围为[0, 30]，Y维度范围为[15， 45]指定范围内的叶子
 *          Double[] removedBound = {0, 30, 15, 45};
 *          Int32 removedNum = tree.Remove(removeBound);
 *
 *  
 * @author lmliang@live.cn       
 *******************************************************************************************/
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RStarTree
{
    /// <summary>
    /// 查询类型
    /// </summary>
    public enum RTreeSearchMode
    {
        Enclosed,   // 内部包围
        Overlapped, // 相交覆盖
    }

    /// <summary>
    /// R*-Tree
    /// </summary>
    partial class RStarTree<TLeaf>
    {
        /// <summary>
        /// 维度
        /// </summary>
        public Int32 Dimension { get; private set; }

        /// <summary>
        /// 树的大小（叶子数目）
        /// </summary>
        public Int32 Size { get; private set; }

        /// <summary>
        /// 构造
        /// 维度 >= 2
        /// M/2 >= m >= 2
        /// </summary>
        /// <param name="dimension">维度</param>
        /// <param name="minChildItems">最小子条目数(m)</param>
        /// <param name="maxChildItems">最大子条目数(M)</param>
        public RStarTree(Int32 dimension, Int32 m, Int32 M)
        {
            Debug.Assert(dimension >= 2);
            Debug.Assert(m > 0 && m >= 2 && m <= M / 2);

            this.Dimension = dimension;
            this.m = m;
            this.M = M;
            this.Size = 0;
        }

        /// <summary>
        /// 插入叶子
        /// </summary>
        /// <param name="leaf">叶子</param>
        /// <param name="bound">包围盒</param>
        /// <returns>成功返回true，否则返回false</returns>
        public Boolean Insert(TLeaf data, Double[] bound)
        {
            if (Dimension != bound.Length / 2)
            {
                Debug.Assert(false);
                return false;
            }

            //叶子
            RTreeLeaf<TLeaf> leaf = new RTreeLeaf<TLeaf>(data, new RTreeBoundingBox(bound));

            if (Root == null)
            {
                // 叶节点
                RTreeNode leafNode = new RTreeNode(Dimension, true);
                leafNode.Items.Add(leaf);
                leafNode.Stretch(leaf);

                // 根节点
                Root = new RTreeNode(Dimension, false);
                Root.Items.Add(leafNode);
                Root.Stretch(leafNode);
            }
            else
            {
                InsertLeaf(leaf, Root, true);
            }

            ++Size;

            return true;
        }

        /// <summary>
        /// 查询所有叶子
        /// </summary>
        /// <returns></returns>
        public TLeaf[] Search()
        {
            if (Root == null)
            {
                //Debug.Assert(Root != null);
                return new List<TLeaf>().ToArray();
            }

            return SearchLeaves(new RTreeBoundingBox(2), (Int32)RTreeSearchMode.Overlapped + 1);
        }

        /// <summary>
        /// 查找
        /// </summary>
        /// <param name="bound">查询范围</param>
        /// <param name="mode">查询模式</param>
        /// <returns>查找到的叶子序列</returns>
        public TLeaf[] Search(Double[] bound, RTreeSearchMode mode = RTreeSearchMode.Overlapped)
        {
            Debug.Assert(bound.Length / 2 == Dimension);

            if (Root == null)
            {
                //Debug.Assert(Root != null);
                return new List<TLeaf>().ToArray();
            }

            RTreeBoundingBox boundBox = new RTreeBoundingBox(bound);

            return SearchLeaves(boundBox, (Int32)mode);
        }

        /// <summary>
        /// 删除指定范围内的叶子
        /// </summary>
        /// <param name="bound">包围盒</param>
        /// <returns>删除叶子数目</returns>
        public Int32 Remove(Double[] bound)
        {
            if (Root == null)
            {
                return 0;
            }

            Int32 before = Size;

            Debug.Assert(Dimension == bound.Length / 2);

            List<RTreeLeaf<TLeaf>> reinsertLeaves = new List<RTreeLeaf<TLeaf>>();
            IRTreeAccepter<TLeaf> accepter = new RTreeEnclosedAccepter<TLeaf>(new RTreeBoundingBox(bound));
            IRTreeRemover<TLeaf> remover = new RTreeAnyLeafRemover<TLeaf>();

            Remove(Root, ref accepter, ref remover, ref reinsertLeaves);

            foreach (RTreeLeaf<TLeaf> leaf in reinsertLeaves)
                InsertLeaf(leaf, Root, true);

            return before - Size;
        }

        /// <summary>
        /// 删除指定叶子
        /// </summary>
        /// <param name="removedLeaf">待删除叶子</param>
        /// <param name="removeDuplicates">是否删除重复项</param>
        /// <returns>删除叶子数目</returns>
        public Int32 Remove(TLeaf removedLeaf, Boolean removeDuplicates)
        {
            if (Root == null)
            {
                return 0;
            }

            Int32 before = Size;

            List<RTreeLeaf<TLeaf>> reinsertLeaves = new List<RTreeLeaf<TLeaf>>();
            IRTreeAccepter<TLeaf> accepter = new RTreeAnyAccepter<TLeaf>();
            IRTreeRemover<TLeaf> remover = new RTreeSpecificLeafRemover<TLeaf>(removedLeaf, removeDuplicates);

            Remove(Root, ref accepter, ref remover, ref reinsertLeaves);

            foreach (RTreeLeaf<TLeaf> leaf in reinsertLeaves)
                InsertLeaf(leaf, Root, true);

            return before - Size;
        }

        /// <summary>
        /// 清空
        /// </summary>
        public void Clear()
        {
            Root = null;
            Size = 0;
        }

        /// <summary>
        /// 插入叶子
        /// </summary>
        /// <param name="leaf">叶节点</param>
        private RTreeNode InsertLeaf(RTreeLeaf<TLeaf> leaf, RTreeNode node, Boolean firstInsert)
        {
            // I4:调整包围盒
            node.Stretch(leaf);

            // I1:选择插入节点
            if (node.IsLeafNode)
            {
                // 当前节点为叶节点则直接加入
                node.Items.Add(leaf);
            }
            else
            {
                // 选择子树插入
                RTreeNode subtree = ChooseSubtree(node, leaf);
                RTreeNode tmpNode = InsertLeaf(leaf, subtree, firstInsert);
                if (tmpNode == null)
                    return null;
                else
                    node.Items.Add(tmpNode);
            }

            // I2:节点多余最大节点数，溢出处理
            if (node.Items.Count > M)
            {
                // I3:溢出处理，向上传递
                return OverflowTreatment(node, firstInsert);
            }
            else
                return null;
        }

        /// <summary>
        /// 选择子树
        /// </summary>
        /// <param name="node">当前节点</param>
        /// <param name="bound">包围盒</param>
        /// <returns>子树节点</returns>
        private RTreeNode ChooseSubtree(RTreeNode node, RTreeBoundingBox bound)
        {
            Debug.Assert(node.Items.Count > 0);

            if (node.IsLeafNode)
                return node;

            RTreeNode chosen = null;

            // 子节点是叶节点
            if ((node.Items[0] as RTreeNode).IsLeafNode)
            {
                // 确定最小覆盖成本 [determine the nearly minimum overlapArea cost]
                node.Items.Sort(new SortItemsByOverlapEnlargement(bound));

                // 确定最小面积成本 [determine the minimum area cost]
                node.Items.Sort(0, Math.Min(node.Items.Count, CHOOSE_SUBTREE_P), new SortItemsByAreaEnlargement(bound));

                chosen = node.Items[0] as RTreeNode;
            }
            else // 子节点非叶节点
            {
                node.Items.Sort(new SortItemsByAreaEnlargement(bound));

                chosen = node.Items[0] as RTreeNode;
            }

            return chosen;
            /* 不适用递归查找到叶节点，在外部递归处理路径节点溢出
            return ChooseSubtree(chosen, bound, ref path);
            */
        }

        /// <summary>
        /// 重新插入节点
        /// </summary>
        /// <param name="node">节点</param>
        private void ReInsert(RTreeNode node)
        {
            Debug.Assert(node.IsLeafNode);
            Debug.Assert(node.Items.Count == M + 1);

            // RI1.RI2:按照中点距离排序
            node.Items.Sort(new SortItemsByCenterDistance(node));

            // RI3:删除子节点
            Int32 removeNum = (Int32)((Double)node.Items.Count * REINSERT_P) > 0 ? (Int32)((Double)node.Items.Count * REINSERT_P) : 1;
            List<RTreeBoundingBox> removed = node.Items.GetRange(node.Items.Count - removeNum, removeNum);
            node.Items.RemoveRange(node.Items.Count - removeNum, removeNum);
            node.UpdateBoundingBox();
     
            // RI4:重新插入节点
            for (int i = removeNum - 1; i >= 0; --i)
            {
                RTreeLeaf<TLeaf> leafNode = removed[i] as RTreeLeaf<TLeaf>;
                InsertLeaf(leafNode, Root, false);
            }
        }

        /// <summary>
        /// 子节点溢出处理
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="firstCall">是否第一次调用</param>
        /// <returns>发生分裂则返回分裂节点，否则返回null</returns>
        private RTreeNode OverflowTreatment(RTreeNode node, bool firstCall)
        {
            // 非根节点且第一次调用，则ReInsert
            if (node != Root && firstCall)
            {
                ReInsert(node);
                return null;
            }
            else
            {
                RTreeNode splitNode = Split(node);

                // 如果是根节点，则创建新的根节点
                if (node == Root)
                {
                    RTreeNode newRoot = new RTreeNode(Dimension, false);
                    newRoot.Items.Add(Root);
                    newRoot.Items.Add(splitNode);
                    newRoot.UpdateBoundingBox();

                    Root = newRoot;
                    return null;
                }
                else
                {
                    // 向上传递
                    return splitNode;
                }
            }
        }

        /// <summary>
        /// 分裂节点
        /// </summary>
        /// <param name="node">待分裂节点</param>
        /// <returns>成功返回分裂后的新节点，否则返回null</returns>
        private RTreeNode Split(RTreeNode node)
        {
            if (node.Items.Count <= M)
            {
                Debug.Assert(false);
                return null;
            }

            Debug.Assert(node.Items.Count == M + 1);

            // 选择最佳分裂维度
            Int32 splitAxis = ChooseSplitAxis(node);
            Debug.Assert(0 <= splitAxis && splitAxis < node.Dimension);

            // 选择最佳分裂点
            Tuple<Boolean, Int32> splitIndex = ChooseSplitIndex(node, splitAxis);
            Debug.Assert(m <= splitIndex.Item2 && splitIndex.Item2 <= M );

            if (splitIndex.Item1)
                node.Items.Sort(new SortItemsByAxisMin(splitAxis));
            else
                node.Items.Sort(new SortItemsByAxisMax(splitAxis));

            // 将子节点加入分裂产生的新节点
            RTreeNode newnode = new RTreeNode(node.Dimension, node.IsLeafNode);
            newnode.Items.AddRange(node.Items.GetRange(splitIndex.Item2, node.Items.Count - splitIndex.Item2));
            newnode.UpdateBoundingBox();

            // 从原节点删除分裂的子节点
            node.Items.RemoveRange(splitIndex.Item2, newnode.Items.Count);
            node.UpdateBoundingBox();

            return newnode;
        }

        /// <summary>
        /// 选择最佳分裂维度
        /// </summary>
        /// <param name="node">分裂节点</param>
        /// <returns>维度索引</returns>
        private Int32 ChooseSplitAxis(RTreeNode node)
        {
            Debug.Assert(node.Items.Count == M + 1);

            Int32 splitAxis = 0;
            Double margin = Double.MaxValue;

            for (int axis = 0; axis < Dimension; ++axis)
            {
                // 按最小值
                node.Items.Sort(new SortItemsByAxisMin(axis));
                Double S = GetSplitMargin(node);
                if (S < margin)
                {
                    margin = S;
                    splitAxis = axis;
                }

                // 按最大值
                node.Items.Sort(new SortItemsByAxisMax(axis));
                S = GetSplitMargin(node);
                if (S < margin)
                {
                    margin = S;
                    splitAxis = axis;
                }
            }

            return splitAxis;
        }
        /// <summary>
        /// 获取分裂边长
        /// </summary>
        /// <param name="node">节点</param>
        /// <returns>边长</returns>
        private Double GetSplitMargin(RTreeNode node)
        {
            Int32 distributions = (M - 2 * m + 2);

            Double minMargin = Double.MaxValue;

            // 分裂部分的包围盒
            RTreeBoundingBox bound1 = new RTreeBoundingBox(node.Dimension);
            RTreeBoundingBox bound2 = new RTreeBoundingBox(node.Dimension);

            for (int k = 1; k <= distributions; ++k )
            {
                bound1.Reset();
                bound2.Reset();

                List<RTreeBoundingBox> s1 = node.Items.GetRange(0, m - 1 + k);
                List<RTreeBoundingBox> s2 = node.Items.GetRange(m - 1 + k, M + 2 - m - k);

                s1.ForEach(delegate(RTreeBoundingBox bound) { bound1.Stretch(bound); });
                s2.ForEach(delegate(RTreeBoundingBox bound) { bound2.Stretch(bound); });

                Double margin = bound1.Margin() + bound2.Margin();
                if (margin < minMargin)
                    minMargin = margin;
            }

            return minMargin;
        }

        /// <summary>
        /// 选择最佳分裂点
        /// </summary>
        /// <param name="node">分裂节点</param>
        /// <param name="splitAxis">分裂维度</param>
        /// <returns>分裂点</returns>
        private Tuple<Boolean, Int32> ChooseSplitIndex(RTreeNode node, Int32 splitAxis)
        {
            Debug.Assert(node.Items.Count == M + 1);
            Debug.Assert(0 <= splitAxis && splitAxis < node.Dimension);

            Int32 splitIndex = 0;
            Boolean splitByMin = true;
            Double overlapArea = Double.MaxValue;
            Double unionArea = Double.MaxValue;

            // 按维度最小值
            node.Items.Sort(new SortItemsByAxisMin(splitAxis));
            Tuple<Int32, Double, Double> ret = GetSplitIndex(node);
            if (ret.Item2 < overlapArea)
            {
                splitIndex = ret.Item1;
                overlapArea = ret.Item2;
                unionArea = ret.Item3;
                splitByMin = true;
            }
            else if (ret.Item2 == overlapArea)
            {
                if (ret.Item3 < unionArea)
                {
                    splitIndex = ret.Item1;
                    overlapArea = ret.Item2;
                    unionArea = ret.Item3;
                    splitByMin = true;
                }
            }

            // 按维度最大值
            node.Items.Sort(new SortItemsByAxisMax(splitAxis));
            ret = GetSplitIndex(node);
            if (ret.Item2 < overlapArea)
            {
                splitIndex = ret.Item1;
                overlapArea = ret.Item2;
                unionArea = ret.Item3;
                splitByMin = false;
            }
            else if (ret.Item2 == overlapArea)
            {
                if (ret.Item3 < unionArea)
                {
                    splitIndex = ret.Item1;
                    overlapArea = ret.Item2;
                    unionArea = ret.Item3;
                    splitByMin = false;
                }
            }

            return new Tuple<Boolean, Int32>(splitByMin, splitIndex);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private Tuple<Int32, Double, Double> GetSplitIndex(RTreeNode node)
        {
            Int32 distribution = (M - 2 * m + 2);

            Int32 index = 0;
            Double overlapArea = Double.MaxValue;
            Double unionArea = Double.MaxValue;

            RTreeBoundingBox bound1 = new RTreeBoundingBox(node.Dimension);
            RTreeBoundingBox bound2 = new RTreeBoundingBox(node.Dimension);

            for (int k = 1; k <= distribution; ++k )
            {
                bound1.Reset();
                bound2.Reset();

                List<RTreeBoundingBox> s1 = node.Items.GetRange(0, m - 1 + k);
                List<RTreeBoundingBox> s2 = node.Items.GetRange(m - 1 + k, M + 2 - m - k);

                s1.ForEach(delegate(RTreeBoundingBox bound) { bound1.Stretch(bound); });
                s2.ForEach(delegate(RTreeBoundingBox bound) { bound2.Stretch(bound); });

                Double overlap = bound1.OverlapArea(bound2);
                Double union = bound1.Area() + bound2.Area();

                // 重叠面积不同时选择小的；相同时选择面积和小的；
                if (overlap > overlapArea)
                {
                    continue;
                }
                else if (overlap < overlapArea)
                {
                    overlapArea = overlap;
                    unionArea = union;
                    index = m - 1 + k;
                }
                else
                {
                    if (union < unionArea)
                    {
                        overlapArea = overlap;
                        unionArea = union;
                        index = m - 1 + k;
                    }
                }
            }

            return new Tuple<Int32, Double, Double>(index, overlapArea, unionArea);
        }


        /// <summary>
        /// 按给定包围盒查找
        /// </summary>
        /// <param name="bound">包围盒</param>
        /// <param name="mode">查询模式</param>
        /// <returns>查找到的叶子序列</returns>
        private TLeaf[] SearchLeaves(RTreeBoundingBox bound, Int32 mode)
        {
            IRTreeAccepter<TLeaf> accepter = null;
            if (mode == (Int32)RTreeSearchMode.Enclosed)
            {
                accepter = new RTreeEnclosedAccepter<TLeaf>(bound);
            }
            else if (mode == (Int32)RTreeSearchMode.Overlapped)
            {
                accepter = new RTreeOverlappedAccepter<TLeaf>(bound);
            }
            else
            {
                accepter = new RTreeAnyAccepter<TLeaf>();
            }

            List<TLeaf> leaves = new List<TLeaf>();
            SearchLeaves(Root, ref leaves, accepter);
            return leaves.ToArray();
        }

        /// <summary>
        /// 查找叶子
        /// </summary>
        /// <param name="node">查找结点</param>
        /// <param name="leaves">叶子集合</param>
        /// <param name="accepter">查找器</param>
        private void SearchLeaves(RTreeNode node, ref List<TLeaf> leaves, IRTreeAccepter<TLeaf> accepter)
        {
            if (!accepter.Accept(node))
                return;

            if (node.IsLeafNode)
            {
                foreach (RTreeLeaf<TLeaf> leaf in node.Items)
                {
                    if (accepter.Accept(leaf))
                        leaves.Add(leaf.Leaf);
                }
            }
            else
            {
                foreach (RTreeNode item in node.Items)
                    SearchLeaves(item, ref leaves, accepter);
            }
        }

        /// <summary>
        /// 删除
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="accepter">接收器</param>
        /// <param name="remover">删除器</param>
        /// <param name="reinsertList">重新插入序列</param>
        /// <returns>如果父节点需要删除当前节点则返回true，否则返回false</returns>
        private Boolean Remove(RTreeNode node, ref IRTreeAccepter<TLeaf> accepter, ref IRTreeRemover<TLeaf> remover, ref List<RTreeLeaf<TLeaf>> reinsertList)
        {
            if (!remover.Continue() || !accepter.Accept(node))
            {
                return false;
            }

            if (node.IsLeafNode)
            {
                for (Int32 i = node.Items.Count - 1; i >= 0 && remover.Continue(); --i)
                {
                    RTreeLeaf<TLeaf> leaf = node.Items[i] as RTreeLeaf<TLeaf>;

                    if (accepter.Accept(leaf) && remover.Remove(leaf))
                    {
                        node.Items.Remove(leaf);
                        node.UpdateBoundingBox();
                        --Size;
                    }
                }
            }
            else
            {
                for (Int32 i = node.Items.Count - 1; i >= 0 && remover.Continue(); --i)
                {
                    RTreeNode item = node.Items[i] as RTreeNode;

                    if (Remove(item, ref accepter, ref remover, ref reinsertList))
                    {
                        node.Items.Remove(item);
                        node.UpdateBoundingBox();
                    }
                }
            }

            // 当前节点条目数少于最小数目，则将剩余叶节点加入重新插入序列，并通知父节点删除自己
            if (node.Items.Count < m)
            {
                if (node.Items.Count > 0)
                    AppendLeavesToReInsertList(node, ref reinsertList);

                node.Reset();

                return true;
            }

            return false;
        }

        /// <summary>
        /// 将叶节点加入重新插入序列
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="reinsertList">序列</param>
        private void AppendLeavesToReInsertList(RTreeNode node, ref List<RTreeLeaf<TLeaf>> reinsertList)
        {
            if (node.IsLeafNode)
            {
                foreach (RTreeLeaf<TLeaf> leaf in node.Items)
                    reinsertList.Add(leaf);
            }
            else
            {
                foreach (RTreeNode item in node.Items)
                    AppendLeavesToReInsertList(node, ref reinsertList);
            }
        }

        /// <summary>
        /// 最小子节点树
        /// </summary>
        private Int32 m;

        /// <summary>
        /// 最大子节点数
        /// </summary>
        private Int32 M;

        /// <summary>
        /// 根节点
        /// </summary>
        private RTreeNode Root = null;

        /// <summary>
        /// ChooseSubtree的参数P
        /// </summary>
        private const Int32 CHOOSE_SUBTREE_P = 32;

        /// <summary>
        /// ReInsert的参数P
        /// </summary>
        private const Double REINSERT_P = 0.3;
    }
}
